package com.ztom.dp;

/**
 * 乘积最大子数组
 * <p>
 * https://leetcode-cn.com/problems/maximum-product-subarray/
 *
 * @author ZhangTao
 */
public class Code12MaxProduct {

    public class Info {
        public int max;
        public int min;
        public int res;

        public Info(int max, int min, int res) {
            this.max = max;
            this.min = min;
            this.res = res;
        }
    }

    public int maxProduct2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 乘积需要考虑负负得正, 因此需要得到前一个位置的最大值和最小值
        return process(nums, nums.length - 1).res;
    }

    private Info process(int[] nums, int i) {
        // 已 i 位置结尾的子数组
        if (i == 0) {
            return new Info(nums[0], nums[0], nums[0]);
        }

        Info pre = process(nums, i - 1);
        int curMax = Math.max(Math.max(pre.max * nums[i], pre.min * nums[i]), nums[i]);
        int curMin = Math.min(Math.min(pre.max * nums[i], pre.min * nums[i]), nums[i]);
        return new Info(curMax, curMin, Math.max(curMax, pre.res));
    }

    public int maxProduct1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] maxDp = new int[n];
        int[] minDp = new int[n];
        int max = nums[0];
        maxDp[0] = nums[0];
        minDp[0] = nums[0];

        for (int i = 1; i < n; i++) {
            maxDp[i] = Math.max(Math.max(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]), nums[i]);
            minDp[i] = Math.min(Math.min(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]), nums[i]);
            max = Math.max(max, maxDp[i]);
        }

        return max;
    }


    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int res = nums[0];
        int max = nums[0];
        int min = nums[0];

        for (int i = 1; i < n; i++) {
            int preMax = max, preMin = min;
            max = Math.max(Math.max(preMax * nums[i], preMin * nums[i]), nums[i]);
            min = Math.min(Math.min(preMax * nums[i], preMin * nums[i]), nums[i]);
            res = Math.max(res, max);
        }

        return res;
    }
}
